#include <vector>
#include <string>
#include <cstdio>

using std::vector;
using std::string;
vector<int> getNext(const string& t)
{
    int j = 0, k = -1;
    std::vector<int> next(t.size() + 1, 0);
    next[0] = -1;
    while (j < t.size())
    {
        if (k == -1 || t[j] == t[k])
            next[++j] = ++k;
        else 
            k = next[k];
    }
    return next;
}
int KMP(const string& s, const string& t, int pos)
{
    int i = pos, j = 0;
    int slen = s.size();
    int tlen = t.size();
    vector<int> next = getNext(t);
    while (i < slen && j < tlen)
    {
        if (j == -1 || s[i] == t[j])
        {
            i++;
            j++;
        }
        else 
        {
            if (j >= 0 && j < tlen)
                j = next[j];
            else 
                break;
        }
    }
    if (j == tlen)
        return i - tlen;
    return -1;
}

int main()
{
    string s = "hello";
    string t = "ll";
    int pos = KMP(s, t, 0);
    printf("%d\n", pos);
    return 0;
}